package Offer.offer2016;

import domain.TreeNode;

public class Test18 {

    public static boolean hasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null)
            return false;
        if (root2 == null) {
            return true;
        }
        boolean result = false;
        if (root1.val == root2.val) {
            result = doesTree1HasTree2(root1, root2);
        }

        if (!result) {
            result = hasSubtree(root1.left, root2);
        }
        if (!result) {
            result = hasSubtree(root1.right, root2);
        }
        return result;
    }

    public static boolean doesTree1HasTree2(TreeNode root1, TreeNode root2) {
        if (root1 == null)
            return false;
        if (root2 == null)
            return true;
        if (root1.val != root2.val) {
            return false;
        }
        return doesTree1HasTree2(root1.left, root2.left) && doesTree1HasTree2(root1.right, root2.right);
    }


}

class IsSubTree {
    public static boolean hasSubTree(TreeNode list1, TreeNode list2) {
        boolean result = false;
        if (list1 != null && list2 != null) {
            if (list1.val == list2.val) {
                result = doesTree1HasTree2(list1, list2);
            }
            if (!result) {
                result = hasSubTree(list1.left, list2);
            }
            if (!result) {
                result = hasSubTree(list1.right, list2);
            }
        }
        return result;
    }

    public static boolean doesTree1HasTree2(TreeNode list1, TreeNode list2) {
        if (list2 == null) {
            return true;
        }
        if (list1 == null) {
            return false;
        }
        if (list1.val != list2.val) {
            return false;
        }
        return doesTree1HasTree2(list1.left, list2.left)
                && doesTree1HasTree2(list1.right, list2.right);
    }
}

